package com.cheung.leetcode.greedy;

import org.junit.jupiter.api.Test;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.greedy
 * @Author :  cheungming
 * @CreateTime : 2024-06-06 09:12:09
 * @Description : 跳跃游戏
 * @Version : 1.0
 */
public class Code45Test {

    public int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }

        // 当前覆盖到的最远位置
        int cur = 0;
        // 下一步覆盖到的最远位置
        int next = 0;
        // 跳跃次数
        int result = 0;

        for (int i = 0; i < nums.length; i++) {
            // 更新下一步覆盖到的最远位置
            next = Math.max(nums[i] + i, next);
            // 跳到当前位置
            if (i == cur) {
                result++;
                // 更新当前覆盖到的最远位置
                cur = next;
                if (cur >= nums.length - 1) {
                    break;
                }
            }
        }

        return result;

    }

    @Test
    public void test1() {
        int[] nums = {2, 3, 1, 1, 4};
        assert jump(nums) == 2;
    }

    @Test
    public void test2() {
        int[] nums = {2, 3, 0, 1, 4};
        assert jump(nums) == 2;
    }
}
